package Algorithm;

public class Day03 {
    //设计链表
    class ListNode {
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
        public ListNode() {

        }
    }

    ListNode dummyhead;
    int size;

    public Day03() {
        dummyhead = new ListNode();
        size = 0;
    }

    public int get(int index) {
        //合法性判断
        if(index < 0 || index > size-1) {
            return -1;
        }
        ListNode cur = dummyhead;
        while(index > 0) {
            cur = cur.next;
            index--;
        }
        return cur.next.val;
    }

    public void addAtHead(int val) {
        ListNode node = new ListNode(val);
        node.next = dummyhead.next;
        dummyhead.next = node;
        size++;
    }

    public void addAtTail(int val) {
        ListNode cur = dummyhead;
        while(cur.next != null) {
            cur = cur.next;
        }
        ListNode node = new ListNode(val);
        cur.next = node;
        size++;
    }

    public void addAtIndex(int index, int val) {
        //合法性判断
        if(index > size) {
            return;
        }
        if(index == size) {
            addAtTail(val);
            return;
        }
        ListNode cur = dummyhead;
        while(index > 0) {
            cur = cur.next;
            index--;
        }
        ListNode node = new ListNode(val);
        node.next = cur.next;
        cur.next = node;
        size++;
    }

    public void deleteAtIndex(int index) {
        if(index < 0 || index > size-1) {
            return;
        }
        ListNode cur = dummyhead;
        while(index > 0) {
            cur = cur.next;
            index--;
        }
        cur.next = cur.next.next;
        size--;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return head;
        }
        ListNode dummyHead = new ListNode();
        dummyHead = head;
        ListNode fast = dummyHead;
        ListNode slow = dummyHead;
        while (n+1 > 0 && fast != null) {
            fast = fast.next;
            n--;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        if (slow.next != null) {
            slow.next = slow.next.next;
        }
        return dummyHead.next;
    }

    public static void main(String[] args) {
        Day03 list = new Day03();
        list.addAtTail(1);
        list.addAtTail(2);
        list.removeNthFromEnd(list.dummyhead.next, 1);
    }
}
